#include "big_int.h"
#include <utility>
#include <sstream>

big_int abs(big_int x)
{
   big_int res = (x < 0) ? -x : x;
   return res;
}

big_int :: big_int() : digits(1, 0), shift(0), negative_sign(false)
{
}

big_int :: big_int(int x) :  digits(1, abs(x)), negative_sign(x < 0), shift(0)
{
}

big_int :: big_int(std :: string str): negative_sign(false), shift(0)
{
   if (str[0] == '-')
   {
      negative_sign = true;
      str = str.substr(1, str.length() - 1);
   }
   int k = str.size() % base_lenght;
   for (int i = str.size(); i - base_lenght >= 0; i -= base_lenght)
   {
      digits.push_back(atoi(str.substr(i - base_lenght, base_lenght).c_str()));
   }
   if (k != 0)
      digits.push_back(atoi(str.substr(0, k).c_str()));
}

big_int& big_int :: operator= (const big_int& x)
{
   digits = x.digits;
   negative_sign = x.negative_sign;
   shift = x.shift;
   return *this;
}

void big_int :: cut_zeros()
{
   while (size() > 1 && digits.back() == 0)
      digits.pop_back();
}

size_t big_int::size() const
{
    return digits.size();
}

int big_int :: find_quot(const big_int& x)
{
   if (*this < x)
      return 0;
   int m, l = 0;
   int r = base;

   while (l + 1 != r)
   {
      m = (l + r) / 2;
      if (*this < x * m)
         r = m;
      else
         l = m;
   }
   return l;
   return 0;
}

void big_int :: swap(big_int& x)
{
   std :: swap(digits, x.digits);
   std :: swap(negative_sign, x.negative_sign);
   std :: swap(shift, x.shift);
}

int big_int :: abs_compare(const big_int& x) const
{
   if (size() - x.size() - x.shift != 0)
      return size() - x.size() - x.shift;
   int i = size() - 1;
   int j = x.size() - 1;
   while ((i >= 0) && (j >= 0))
   {
      int diff = digits[i] - x.digits[j];
      if (diff != 0)
         return diff;
      i--;
      j--;
   }
   return 0;
}

int big_int :: compare (const big_int& x) const
{
   big_int cur = *this;
   if (!cur.negative_sign & !x.negative_sign)
      return cur.abs_compare(x);
   if (cur.negative_sign & x.negative_sign)
      return x.abs_compare(cur);
   if (cur.negative_sign & !x.negative_sign)
      return -1;
   if (!cur.negative_sign & x.negative_sign)
      return 1;

   return 0;
}

bool big_int :: operator <(const big_int& x) const
{
   return compare(x) < 0;
}

bool big_int :: operator >(const big_int& x) const
{
   return compare(x) > 0;
}

bool big_int :: operator <=(const big_int& x) const
{
   return compare(x) <= 0;
}

bool big_int :: operator >=(const big_int& x) const
{
   return compare(x) >= 0;
}

bool big_int :: operator ==(const big_int& x) const
{
   return compare(x) == 0;
}

bool big_int :: operator !=(const big_int& x) const
{
   return compare(x) != 0;
}

big_int big_int :: operator -() const
{
   big_int res = *this;
   if (res != 0) 
      res.negative_sign = !res.negative_sign;
   return res;
}

big_int& big_int :: operator +=(const big_int& x)
{
   if(x == 0)
      return *this;

   big_int cur= *this;
   if (cur.negative_sign)
      return (*this = -((-cur) + (-x)));
   if (abs(cur) < abs(x))
      return (*this = (x + cur));
   cur.negative_sign = false;
   shift = std :: min(cur.shift, x.shift);
   size_t new_size = std :: max(cur.size() + cur. shift, x.size() + x.shift) - cur.shift;
   my_container new_digits(new_size + 1, 0);
   digits = new_digits;
   int sign = (x.negative_sign == true) ? -1 : 1;
   int carry = 0;
   
   for (size_t i = 0; i < size(); i++)
   {
      int ans = 0;
      if ((cur.shift <= shift + static_cast<int>(i)) && (shift + i < cur.shift + cur.size()))
         ans += cur.digits[i + shift - cur.shift];
      if ((x.shift <= shift + static_cast<int>(i)) && (shift + i < x.shift + x.size()))
         ans += x.digits[i + shift - x.shift] * sign;
      
      ans+= carry;
      carry = 0;
      if (ans >= base)
      {
         ans-= base;
         carry = 1;
      }
      if (ans <  0)
      {
         ans+= base;
         carry = -1;
      }
      digits[i] = ans;
   }
   cut_zeros();
   return *this;
}

big_int big_int :: operator +(const big_int& x) const
{
   big_int res = *this;
   return res += x;
}

big_int& big_int :: operator -=(const big_int& x)
{
   return (*this) += (-x);
}

big_int big_int :: operator- (const big_int& x) const
{
   big_int res = *this;
   return res -= x;
}

big_int& big_int :: operator *=(const big_int& x)
{
   if (x == 1)
      return *this;
   big_int cur = *this;

   shift = cur.shift + x.shift;
   if ((cur != 0) && (x != 0))
      negative_sign = cur.negative_sign ^ x.negative_sign;
   size_t new_size = cur.size() + x.size() + 1;
   my_container new_digits(new_size, 0);
   digits = new_digits;

   for (size_t i = 0; i < cur.size(); i++)
   {
      size_t carry = 0;
      for (size_t j = 0; j < x.size(); j++)
      {
         long long ans = static_cast<long long>(cur.digits[i]) * x.digits[j];
         digits[i + j] += ans % base + carry;
         carry = static_cast<int>(ans / base) + digits[i + j] / base;
         digits[i + j] %= base;
      }
      digits[i + x.size()] += carry;
      carry = digits[i + x.size()] / base;
      digits[i + x.size()] %= base;
      if (carry != 0)
         digits[i + x.size() + 1] = carry;
      else
         digits[i + x.size() + 1] = 0;
   }
   cut_zeros();
   return (*this);
}

big_int big_int :: operator* (const big_int& x) const
{
   big_int res = *this;
   return (res *= x);
}


big_int& big_int::operator <<=(size_t val)
{
   shift += val;
   return *this;
}

big_int operator <<(const big_int& x, size_t val)
{
   big_int t = x;
   return t <<= val;
}

big_int& big_int::operator >>=(size_t val)
{
   shift -= val;
   return *this;
}

big_int operator >>(const big_int& x, size_t val)
{
   big_int t = x;
   return t >>= val;
}

std :: pair <big_int, big_int> big_int :: divide(const big_int& x) const
{
   big_int cur = *this;
   if (x == 0)
      throw  std ::runtime_error("division by zero!");
   if (abs(cur) < abs(x))
      return std :: make_pair<big_int, big_int> (big_int(0), cur);
   std :: pair<big_int, big_int> res(0, 0);
   my_container quotient(1, 0);
   if (cur != 0)
      res.first.negative_sign = cur.negative_sign ^ x.negative_sign;
   res.second.shift = cur.shift;
   res.first.shift = cur.shift - x.shift;
   big_int t = x << (cur.size() - x.size());

   while (t.shift >= 0)
   {
      int quot = cur.find_quot(t);
      quotient.push_back(quot);
      cur = cur - t * quot;
      t >>= 1;
   }
   quotient.reverse();
   res.first.digits = quotient;
   res.first.cut_zeros();
   res.second = (negative_sign == true) ? -cur : cur;
   return res;
}

big_int& big_int :: operator /= (const big_int& x)
{
   return (*this = divide(x).first);
}

big_int& big_int :: operator %= (const big_int& x)
{
   return (*this = divide(x).second);
}

big_int big_int::operator / (const big_int& x)const
{
   big_int res = *this;
   return res /= x;
}

big_int big_int::operator % (const big_int& x)const
{
   big_int res = *this;
   return res %= x;
}

std :: istream& operator >>(std :: istream &in, big_int& x)
{
   while (isspace(in.peek()))
      in.get();
   if (in.eof())
   {
      in.setstate(std::ios::failbit);
      return in;
   }
   std::string str = "";
   if ((in.peek() == '+') || (in.peek() == '-'))
   {
      if (in.peek() == '-')
         str += '-';
      in.get();
   }
   if (!isdigit(in.peek()))
   {
      in.setstate(std::ios::failbit);
      return in;
   }
   while (isdigit(in.peek()))
   {
      str.push_back(static_cast<char>(in.get()));
   }
   x = big_int(str);
   return in;
}

std :: ostream& operator <<(std :: ostream &out, const big_int& x)
{
   size_t x_size = x.size();
   std::string zeros(x.base_lenght, '0');
   if (x.negative_sign == true)
      out << '-';
   out << x.digits[x.size() - 1];

   std::streamsize old_width = out.width();
   char old_fill = out.fill();

   for (int i = x.size() - 2; i >= 0; i--)
      out << std::setw(10) << std::setfill('0') << x.digits[i];

   out.width(old_width);
   out.fill(old_fill);
   return out;
}

